This invention relates to an arrangement and method for routing packet traffic in a communications system incorporating non-geostationary satellite nodes, and to an addressing scheme or protocol for facilitating routing within the network.
Conventional telecommunications networks comprise a number of nodes or switches interconnected by wireline or wireless links. Within such networks, traffic between terminals is routed via appropriate nodes and paths. As the topology of the network is substantially fixed, each node can be provided with a permanent or semi-permanent set of routing tables to facilitate traffic routing. Traditionally these networks carried voice traffic, but there is now an increasing interest in data transmission and in particular in packet switching. There are two main types of packet switching, namely connection-oriented packet switching and connectionless packet switching.
Connectionless network operation has been traditionally used in data communications in order to achieve two objectives, firstly to allow client/server operation between endpoints of a network with all intelligence distributed to the endpoints and secondly to allow topological change within the network to occur without the network endpoints needing to be aware that a change has happened. Networks based on the Internet Protocol (IP) are typical embodiments of these principles. Similar principles are embodied in wireless networks in order to avoid the need for explicit connection hand-overs due to the physical mobility of users or systems.
Communications systems are now being developed in which the system nodes comprise a constellation of non-geostationary satellites, e.g. low earth orbit (LEO) satellites. These systems comprise a ground segment incorporating e.g. ground stations, gateways and user terminals, and a space segment comprising the satellite network in which each satellite functions as a switch or a router. It will be appreciated that the topology of such a system is constantly changing as the satellites move relative to the earth""s surface and to each other. In a proposed system, a large number of satellite communications nodes are placed into circumpolar orbits, there being a number of satellites evenly distributed around each orbit so as to provide coverage of much or all of the global surface. Communication with the ground is effected via up-links and down-links to ground stations. Movement of the satellites relative to the ground stations is accommodated by appropriate hand-over procedures. A typical system of this type comprises two hundred and eighty eight satellites divided into twelve orbital planes for the initial phase, this phase being planned to cover 95% of the landmass. Further satellites may be added in the future. The system embodies inter-satellite links (ISL) not only for intra-plane and inter-plane node communications, but also at the cross-seam. Some of these ISLs can be turned on or off at appropriate times. The space segment of the satellite network results in a geodesic topology network that provides good tolerance to faults and congestion and has a symmetrical structure.
Usually these networks rely on connectionless packet switching in order to avoid the need both to store connection state information and to preserve sequence integrity of the packets.
A particular problem in such a system is that of routing traffic between two ground based terminals via a succession of satellite nodes. It will be appreciated that, routing in a network that is changing topology rapidly because the satellite coverage is time varying, the inter-satellite links are dynamic. Depending on the satellite position, some of these links can be off or on, and some are always on. It will also be appreciated that, because the satellites are moving thus constantly changing the network topology in a complex manner, a routing table based routing would require continual updates. Moreover, an accurate routing would require every satellite to be well aware of the topological changes in the space segment. This could be done by storing all the information in the satellites, but this would be very costly since the topological changes are extremely complex even if there are in principle predictable and a large amount of information storage and processing would thus be required. Another way would be to require each satellite to send topological information to its neighbours (for example). This also would be very costly in terms of overheads due to the fast pace at which the topology is changing.
Routing in a connectionless packet switched network is a function that relies on an addressing scheme. Smart addressing scheme can ease a lot the burden of the routing function.
A discussion of satellite communications routing techniques is provided by Markus Werner et al, ATM-Based Routing in LEO/MEO Satellite Networks with Inter-satellite Links. IEEE Journal on Selected Areas in Communications, January 1997, and by Markus Werner, A Dynamic Routing Concept for ATM-Based Satellite Personal Communication Networks. IEEE Journal on Selected Areas in Communications, October 1997.
Reference is also directed to our co-pending application Ser. No. 09/017,360, the contents of which are incorporated herein by reference, and which describes diversion routing of packet traffic in a satellite communications system.
An object of the invention is to provide an improved arrangement and method for addressing and routing in satellite communications networks.
According to a first aspect, the invention provides a hierarchical addressing protocol for a communications network incorporating satellite nodes, the protocol being based on a Gray code in which the ground segment of the network is partitioned into sectors each represented by a respective Gray code.
Each sector is further partitioned into sub-sectors and each sub-sector in cells. The first Gray code representing the sector transforms a three dimensional problem into a two dimensional one.
According to another aspect of the invention, there is provided a hierarchical addressing scheme for a packet communications network comprising a plurality of sectors each sector being partitioned into sub-sectors and each sub-sector into cells serviced via communications nodes whereby communications packets are routed, wherein each network sector is allocated a respective binary Gray code address, wherein adjacent sectors within the network have Gray codes differing by one bit.
According to another aspect of the invention, there is provided a satellite packet communications system comprising a plurality of ground based terminals disposed in cells contained in sectors and serviced via satellite communications nodes, wherein said cells are provided each with an address incorporating a hierarchical addressing scheme based on binary Gray codes, and wherein routing of a communications packet addressed to a said terminal within a said cell is performed in a satellite node by comparison of the packet address with corresponding addresses stored in the satellite.
The addresses stored in the satellite are the ones of the cells currently covered by the satellite as well as those of the sectors and sub-sectors currently partly covered by the satellite. This routing allows the packet to be transported by the space segment up to the cell comprising the destination terminal or gateway. Further addressing and routing is necessary to route the packet up to its destination. The comparison performed in the satellite of the address of destination cell of the packet with the stored addresses is done in a hierarchical way (to simplify it) and the number and bit position of the difference between said codes is used to determine the direction of routing of the packet to another satellite (through the appropriate ISL) or to its destination cell.
In a preferred embodiment, means are provided for between appropriate ISLs if the above scheme provides a choice of more than one ISL. In that case, the ISL can be chosen using shortest queue or other criteria.
According to another aspect of the invention, there is provided a satellite packet communications system comprising a plurality of ground based terminals serviced via satellite communications nodes, wherein said cells are provided each with an address incorporating the above hierarchical addressing scheme based on binary Gray codes, and wherein routing of a communications packet addressed to a said terminal within a said cell is performed in a satellite by comparison of the packet address with corresponding addresses stored in the satellite.
The addresses stored in the satellite are the ones of the cells currently covered by the satellite as well as those of the sectors and sub-sectors currently partly covered by the satellite plus the addresses of the sectors and sub-sectors also partly covered by the neighbouring satellites. This routing allows the packet to be transported by the space segment up to the cell comprising the destination terminal or gateway. Further addressing and routing is necessary to route the packet up to its destination. The comparison performed in the satellite of the address of the destination cell of the packet with the stored addresses is done in a hierarchical way (to simplify it) and the number and bit position of the difference between said codes is used to determine the direction of routing of the packet to another satellite (through the appropriate ISL) or to its destination cell.
According to another aspect of the invention, there is provided a method of routing packet traffic in a communications network serving a plurality of service regions and comprising a plurality of non-stationary nodes interconnected via inter-nodal links, the method comprising allocating to each said service region a respective binary Gray code element, providing said Gray code element as a destination address in an information packet intended for that service region, and determining within a said node the difference between said Gray code and a corresponding code stored at the node whereby to determine from the number and bit position of the difference between said codes being used to determine the direction of routing of the packet to another system node or to its destination sector.
According to another aspect of the invention there is provided a method of routing of packet communications traffic at a satellite node in a communications network comprising a constellation of non-geostationary satellites servicing a plurality of ground based cells via up-links and down-links, there being inter-satellite communications links between adjacent satellites, the method comprising providing a said packet with a destination address incorporating binary Gray codes corresponding to the destination cell of that packet, and, at a said node, comparing the Gray code address of that packet with address codes corresponding to the current position of the satellite so as to provide a simple determination of the direction in which that packet should be routed to an adjacent satellite over a said inter-satellite link.
The technique provides a routing strategy that is simple, robust, efficient, that does not require a large amount information to be stored in the satellite and does not require a large number of exchanges of information between satellites.